GATE CSE 2011
Q21.
An undirected graph G(V, E) contains n (n>2) nodes named v1 , v2 ,...,vn. Two nodes vi , vj are connected if and only if 0\lt |i-j|\leq2. Each edge (vi,vj ) is assigned a weight i+j. A sample graph with n=4 is shown below. The length of the path from v5 to v6 in the MST of previous question with n = 10 isQ23.
A deterministic finite automation (DFA)D with alphabet \Sigma= {a,b} is given below Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?Q24.
Definition of a language L with alphabet {a} is given as following L={a^{nk} |k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?Q25.
Consider two binary operators '\uparrow 'and '\downarrow' with the precedence of operator \downarrow being lower than that of the operator \uparrow . Operator \uparrow is right associative while operator \downarrow is left associative. Which one of the following represents the parse tree for expression (7 \downarrow 3 \uparrow4 \uparrow 3 \downarrow2)?Q26.
Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each with combinational circuit only. The pipeline registers are required between each stage and at the end of the last stage. Delays for the stages and for the pipeline registers are as given in the figure. What is the approximate speed up of the pipeline in steady state under ideal conditions when compared to the corresponding non-pipeline implementation?Q27.
K4 and Q3 are graphs with the following structures Which one of the following statements is TRUE in relation to these graphs?Q28.
If the difference between the expectation of the square of random variable (E[X^{2}]) and the square of the expectation of the random variable (E[X^{2}]) is denoted by R thenQ29.
If two fair coins are flipped and at least one of the outcomes is known to be a head, what is the probability that both outcomes are heads?Q30.
A deck of 5 cards (each carrying a distinct number from 1 to 5) is shuffled thoroughly. Two cards are then removed one at a time from the deck. What is the probability that the two cards are selected with the number on the first card being one higher than the number on the second card?